/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<ListNode*> v1, v2, res;
        while (l1) {
            v1.push_back(l1);
            l1 = l1->next;
        }
        while (l2) {
            v2.push_back(l2);
            l2 = l2->next;
        }

        int i = 0, j = 0, t = 0;
        while (i < v1.size() || j < v2.size() || t != 0) {
            if (i < v1.size()) {
                t += v1[i++]->val;
            }
            if (j < v2.size()) {
                t += v2[j++]->val;
            }

            res.push_back(new ListNode(t % 10));
            t /= 10;
        }

        while (res.size() != 1 && res.back()->val == 0) res.pop_back();

        for (int i = 1; i < res.size(); ++i) {
            res[i - 1]->next = res[i];
        }
        res.back()->next = nullptr;

        return res.front();
    }
};